/**
 * 327. 区间和的个数
 * https://leetcode-cn.com/problems/count-of-range-sum/
 * 进阶：归并排序
 */
public class Solutions_327 {
    public static void main(String[] args) {
        int[] nums = {-2, 5, -1};
        int lower = -2, upper = 2;  // output: 3  {{0, 0}, {2, 2}, {0, 2}}

//        int[] nums = {0, 0};
//        int lower = 0, upper = 0;  // output: 3  {{0, 0}, {1, 1}, {0, 1}}

        int result = countRangeSum(nums, lower, upper);
        System.out.println(result);
    }

    /**
     * 解法一：暴力法（174ms）
     */
    public static int countRangeSum(int[] nums, int lower, int upper) {
        int res = 0;
        long sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum >= lower && sum <= upper) {
                    // [i, j] 的元素和，在 [lower, upper] 中
                    res ++;
                }
            }
        }
        return res;
    }
}
